package com.chl.sort.other;

/**
 * 归并排序 - 稳定
 * 核心
 * 		分组交换排序
 * 
 * 思想
 * 		归并排序是建立在归并操作上的一种有效的排序算法。
 *		该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
 *		将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
 *		若将两个有序表合并成一个有序表，称为2-路归并。
 *       
 * 算法描述
 * 		把长度为n的输入序列分成两个长度为n/2的子序列；
 * 		对这两个子序列分别采用归并排序；
 * 		将两个排序好的子序列合并成一个最终的排序序列。
 * @author 陈宏亮
 *
 */
public class Sort05Merger {
	static int[] arrs;
	static int[] tmps;

	public static void sort(int[] arrs) {
		Sort05Merger.arrs = arrs;
		tmps = new int[arrs.length];
		recurrenceSort(0, arrs.length - 1);
	}

	/**
	 * 递归法
	 * 
	 * @param arrs
	 * @param start
	 * @param end
	 */
	private static void recurrenceSort(int start, int end) {
		if (start == end) {
			return;
		}
		int middle = (start + end) / 2;
		int j = middle + 1;
		int i = start;
		int len = (end - start + 1);
		recurrenceSort(start, middle);
		recurrenceSort(middle + 1, end);
		for (int n = 0; n < len; n++) {
			if (i > middle) {
				tmps[n] = arrs[j];
				j++;
			} else if (j > end) {
				tmps[n] = arrs[i];
				i++;
			} else if (arrs[i] > arrs[j]) {
				tmps[n] = arrs[j];
				j++;
			} else {
				tmps[n] = arrs[i];
				i++;
			}
		}
		
		for (int n = 0; n < len; n++) {
			arrs[start] = tmps[n];
			start++;
		}
	}
}
